package ca.etsmtl.log320lab1;

import java.util.ArrayList;

public class Heap {

	private static ArrayList<CharFrequency> list;  
	public static  ArrayList<CharFrequency> heapSort(ArrayList<CharFrequency> array){
		list = array;
	        for(int i=list.size()-1/2;i>=0;i--){ 
	        	heapify(list,i); 
	        }  
		return list;
	}	
	private static void heapify(ArrayList<CharFrequency> acf, int i){ 
		int left=2*i; 
		int right=2*i+1; 
		int largest;
        if(left <= list.size()-1 && getNode(acf,left).compareTo(getNode(acf,i)) >= 0)
            largest=left; 
        else
            largest=i;
        
        if(right <= list.size()-1 && getNode(acf,right).compareTo(getNode(acf,largest)) >= 0)
            largest=right;  
            
        if(largest!=i){ 
            exchange(i,largest); 
            heapify(acf, largest); 
        } 
    } 
	private static CharFrequency getNode(ArrayList<CharFrequency> CharFrequencyList, int position)
	{
		return CharFrequencyList.get(position);
	}
    private static void exchange(int i, int j){ 
    	CharFrequency t=list.get(i); 
        list.set(i, list.get(j)); 
        list.set(j, t); 
    }

}
